//如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数
//值排序之后中间两个数的平均值。 
//
// 例如， 
//
// [2,3,4] 的中位数是 3 
//
// [2,3] 的中位数是 (2 + 3) / 2 = 2.5 
//
// 设计一个支持以下两种操作的数据结构： 
//
// 
// void addNum(int num) - 从数据流中添加一个整数到数据结构中。 
// double findMedian() - 返回目前所有元素的中位数。 
// 
//
// 示例 1： 
//
// 输入：
//["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
//[[],[1],[2],[],[3],[]]
//输出：[null,null,null,1.50000,null,2.00000]
// 
//
// 示例 2： 
//
// 输入：
//["MedianFinder","addNum","findMedian","addNum","findMedian"]
//[[],[2],[],[3],[]]
//输出：[null,null,2.00000,null,2.50000] 
//
// 
//
// 限制： 
//
// 
// 最多会对 addNum、findMedian 进行 50000 次调用。 
// 
//
// 注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-
//stream/ 
// Related Topics 设计 双指针 数据流 排序 堆（优先队列） 👍 315 👎 0

package leetcode.editor.offer;

import java.util.*;

class ShuJuLiuZhongDeZhongWeiShuLcof {
    public static void main(String[] args) {
        MedianFinder solution = new ShuJuLiuZhongDeZhongWeiShuLcof().new MedianFinder();
        solution.addNum(1);
        solution.addNum(2);
        solution.addNum(3);
        System.out.println(solution.findMedian());
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 41 数据流中的中位数
    class MedianFinder {

 /*       List<Integer> list;
        int[] array;

        *//**
         * initialize your data structure here.
         *//*
        public MedianFinder() {
            list = new ArrayList<>();
        }

        public void addNum(int num) {
            list.add(num);
            array = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                array[i] = list.get(i);
            }
        }

        public double findMedian() {
            quickSort(array, 0, array.length - 1);
            int temp = array.length / 2 - 1;
            if (array.length % 2 == 0) {
                double result = (array[temp] + array[temp + 1]) / 2.0;
                return result;
            } else {
                return array[temp + 1];
            }
        }

        void quickSort(int[] nums, int l, int r) {
            if (l >= r) {
                return;
            }

            int i = l, j = r;
            while (i < j) {
                while (i < j && nums[l] <= nums[j]) j--;
                while (i < j && nums[l] >= nums[i]) i++;
                swap(nums, i, j);
            }
            swap(nums, l, i);

            quickSort(nums, l, i - 1);
            quickSort(nums, i + 1, r);
        }

        public void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }*/

        /**
         * 大顶堆和小顶堆实现
         */
        /*Queue<Integer> A, B;

        public MedianFinder() {
            A = new PriorityQueue<>();  // 小顶堆，存储较大的一半的值
            B = new PriorityQueue<>((x, y) -> y - x);   // 大顶堆，存储较小的一半
        }

        public void addNum(int num) {
            if (A.size() != B.size()) {
                // 如果两个堆的大小不相等，那么此时就为奇数
                // 先将num入A，排好序后，取出A中最小的，再入B
                A.add(num);
                B.add(A.poll());
            } else {
                // 如果两个堆的大小相等，那么此时就为偶数
                // 与上相反
                B.add(num);
                A.add(B.poll());
            }
        }

        public double findMedian() {
            // 注意此时不能使用poll，poll出队列之后，后面就乱序了
            return A.size() == B.size() ? (A.peek() + B.peek()) / 2.0 : A.peek();
        }*/

        Queue<Integer> A, B;

        public MedianFinder() {
            A = new PriorityQueue<>((o1, o2) -> o2 - o1);
            B = new PriorityQueue<>();
        }

        public void addNum(int num) {
            if (A.size() != B.size()) {
                A.offer(num);
                B.offer(A.poll());
            } else {
                B.offer(num);
                A.offer(B.poll());
            }
        }

        public double findMedian() {
            if (A.size() == B.size()) {
                return (A.peek() + B.peek()) / 2.0;
            } else if (A.size() > B.size()) {
                return A.peek();
            } else return B.peek();
        }

    }

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
